package com.lhcai.nk.medium;

/**
 * @author lhcstart
 * @create 2023-02-21 15:28
 */

import java.util.*;
/**
 * 描述
 * 给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才能出站。
 * 要求输出所有火车出站的方案，以字典序排序输出。
 * 数据范围：1≤n≤10
 * 进阶：时间复杂度：O(n!) ，空间复杂度：O(n)
 * 输入描述：
 * 第一行输入一个正整数N（0 < N <= 10），第二行包括N个正整数，范围为1到10。
 * 输出描述：
 * 输出以字典序从小到大排序的火车出站序列号，每个编号以空格隔开，每个输出序列换行，具体见sample。
 */
public class HJ77 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            l.clear();//静态变量，每次先清空
            int n = sc.nextInt();
            int[] arr = new int[n];
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }

            solution(arr, 0, stack, "", 0);
            Collections.sort(l);
            for (String s : l) {
                System.out.println(s);
            }
        }
    }

    public static ArrayList<String> l = new ArrayList();//存放所有的出站顺序

    public static void solution(int[] arr,//存放进站顺序的数组
                                int i, //火车的下标索引
                                Stack<Integer> stack,//栈
                                String str,//火车的出站顺序
                                int n) {//出战的火车数
        //当火车全部出站，结束循环，将结果放入list
        if (n == arr.length) {
            l.add(str);//
            return;
        }

        //出站
        if (!stack.isEmpty()) {
            int temp = stack.pop();
            solution(arr, i, stack, str + temp + " ", n + 1);//出站，n+1
            stack.push(temp);//恢复现场
        }
        //进站，数组中的火车每经历一遍
        if (i < arr.length) {
            stack.push(arr[i]);
            solution(arr, i + 1, stack, str, n);//进站，i+1
            stack.pop();//恢复现场
        }
    }
}